class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 使用递归的方式来处理
        return merge(lists, 0, lists.length - 1);
    }


    private ListNode merge(ListNode[] lists, int start, int end) {
        // 处理边界情况
        if (start > end) { // 不存在链表
            return null;
        }
        if (start == end) { // 只有一个链表
            return lists[start];
        }

        // 1、递归分解
        int mid = (start + end) / 2;
        ListNode l1 = merge(lists, start, mid);
        ListNode l2 = merge(lists, mid + 1, end);

        // 2、合并两个有序链表
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead, cur1 = l1, cur2 = l2;
        // 处理两者都有的情况
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        // 处理单独一个链表的情况
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        return newHead.next;
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}